{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #相似字符串组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSimilarGroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #相似字符串组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果交换字符串&nbsp;<code>X</code> 中的两个不同位置的字母，使得它和字符串&nbsp;<code>Y</code> 相等，那么称 <code>X</code> 和 <code>Y</code> 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。</p>\n",
    "\n",
    "<p>例如，<code>&quot;tars&quot;</code> 和 <code>&quot;rats&quot;</code> 是相似的 (交换 <code>0</code> 与 <code>2</code> 的位置)；&nbsp;<code>&quot;rats&quot;</code> 和 <code>&quot;arts&quot;</code> 也是相似的，但是 <code>&quot;star&quot;</code> 不与 <code>&quot;tars&quot;</code>，<code>&quot;rats&quot;</code>，或 <code>&quot;arts&quot;</code> 相似。</p>\n",
    "\n",
    "<p>总之，它们通过相似性形成了两个关联组：<code>{&quot;tars&quot;, &quot;rats&quot;, &quot;arts&quot;}</code> 和 <code>{&quot;star&quot;}</code>。注意，<code>&quot;tars&quot;</code> 和 <code>&quot;arts&quot;</code> 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。</p>\n",
    "\n",
    "<p>给定一个字符串列表 <code>strs</code>。列表中的每个字符串都是 <code>strs</code> 中其它所有字符串的一个&nbsp;<strong>字母异位词&nbsp;</strong>。请问 <code>strs</code> 中有多少个相似字符串组？</p>\n",
    "\n",
    "<p><strong>字母异位词（anagram）</strong>，一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [&quot;tars&quot;,&quot;rats&quot;,&quot;arts&quot;,&quot;star&quot;]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [&quot;omv&quot;,&quot;ovm&quot;]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= strs.length &lt;= 300</code></li>\n",
    "\t<li><code>1 &lt;= strs[i].length &lt;= 300</code></li>\n",
    "\t<li><code>strs[i]</code> 只包含小写字母。</li>\n",
    "\t<li><code>strs</code> 中的所有单词都具有相同的长度，且是彼此的字母异位词。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp; &nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 839&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/similar-string-groups/\">https://leetcode-cn.com/problems/similar-string-groups/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [H6lPxb](https://leetcode.cn/problems/H6lPxb/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [H6lPxb](https://leetcode.cn/problems/H6lPxb/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"tars\",\"rats\",\"arts\",\"star\"]', '[\"omv\",\"ovm\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        def isSimilar(str1, str2):\n",
    "            unlikeNum = len(str1)\n",
    "            for i in range(unlikeNum):\n",
    "                if str1[i] == str2[i]:\n",
    "                    unlikeNum = unlikeNum - 1\n",
    "            return unlikeNum <= 2\n",
    "\n",
    "        groups = []\n",
    "        while len(strs) > 0:\n",
    "            aGroup = [strs[0]]\n",
    "            strs.remove(strs[0])\n",
    "            groupIndex = 0\n",
    "            while groupIndex < len(aGroup):\n",
    "                strIndex = 0\n",
    "                while strIndex < len(strs):\n",
    "                    if isSimilar(aGroup[groupIndex], strs[strIndex]):\n",
    "                        aGroup.append(strs[strIndex])\n",
    "                        strs.remove(strs[strIndex])\n",
    "                    else:\n",
    "                        strIndex = strIndex + 1\n",
    "                groupIndex = groupIndex + 1\n",
    "            groups.append(aGroup)\n",
    "        return len(groups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        def check(wordx,wordy):\n",
    "            wn = len(wordx)\n",
    "            cnt = 0\n",
    "            for i in range(wn):\n",
    "                if wordx[i] != wordy[i]:\n",
    "                    cnt += 1\n",
    "                    if cnt > 2:\n",
    "                        return False\n",
    "            return cnt == 0 or cnt == 2\n",
    "        \n",
    "        def bfs(sx):\n",
    "            q = deque()\n",
    "            q.append(sx)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                for y in range(n):\n",
    "                    if not vis[y] and check(strs[x],strs[y]):\n",
    "                        vis[y] = True\n",
    "                        q.append(y)\n",
    "\n",
    "        n = len(strs)\n",
    "        vis = [False for _ in range(n)]\n",
    "        cnt = 0\n",
    "        for x in range(n):\n",
    "            if not vis[x]:\n",
    "                vis[x] = True\n",
    "                bfs(x)\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        def check(x,y):\n",
    "            nx = len(x)\n",
    "            cnt = 0\n",
    "            for i in range(nx):\n",
    "                if x[i] != y[i]:\n",
    "                    cnt += 1\n",
    "                if cnt > 2:\n",
    "                    return False\n",
    "            return cnt == 0 or cnt == 2\n",
    "        \n",
    "        def bfs(t):\n",
    "            q = deque()\n",
    "            q.append(t)\n",
    "            vis[t] = True\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                for y in range(n):\n",
    "                    if not vis[y] and check(strs[x],strs[y]):\n",
    "                        vis[y] = True\n",
    "                        q.append(y)\n",
    "        \n",
    "        n = len(strs)\n",
    "        vis = [False for _ in range(n)]\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                vis[i] = True\n",
    "                bfs(i)\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.n = n\n",
    "        self.father = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, u):\n",
    "        if self.father[u] != u:\n",
    "            fu = self.find(self.father[u])\n",
    "            self.father[u] = fu\n",
    "        return self.father[u]\n",
    "\n",
    "    def union(self, u, v):\n",
    "        fu = self.find(u)\n",
    "        fv = self.find(v)\n",
    "        if fu != fv:\n",
    "            self.father[fu] = fv\n",
    "    \n",
    "    def count(self):\n",
    "        return sum(1 for i in range(self.n) if i == self.father[i])\n",
    "\n",
    "def check(s1, s2):\n",
    "    n = len(s1)\n",
    "    count = 0\n",
    "    for i in range(n):\n",
    "        if s1[i] != s2[i]:\n",
    "            count += 1\n",
    "    return count == 0 or count == 2\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        uf = UnionFind(n)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if check(strs[i], strs[j]):\n",
    "                    uf.union(i, j)\n",
    "        return uf.count()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        def isSimilar(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        groups = []\n",
    "        while len(strs) > 0:\n",
    "            aGroup = [strs[0]]\n",
    "            strs.remove(strs[0])\n",
    "            groupIndex = 0\n",
    "            while groupIndex < len(aGroup):\n",
    "                strIndex = 0\n",
    "                while strIndex < len(strs):\n",
    "                    if isSimilar(aGroup[groupIndex], strs[strIndex]):\n",
    "                        aGroup.append(strs[strIndex])\n",
    "                        strs.remove(strs[strIndex])\n",
    "                    else:\n",
    "                        strIndex = strIndex + 1\n",
    "                groupIndex = groupIndex + 1\n",
    "            groups.append(aGroup)\n",
    "        return len(groups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        stack = len(strs)\n",
    "        def conclude(x, y):         \n",
    "            count = 0         \n",
    "            if count <=2:\n",
    "                for i in range(len(strs[x])):                              \n",
    "                    if strs[x][i] != strs[y][i]:\n",
    "                        count +=1\n",
    "            return count <=2\n",
    "\n",
    "        father = []\n",
    "        for i in range(len(strs)):\n",
    "            father.append(i)\n",
    "        \n",
    "        def find(x):\n",
    "            if x != father[x]:\n",
    "                father[x] = find(father[x])\n",
    "            return  father[x]\n",
    "        \n",
    "\n",
    "        def union(x, y):\n",
    "            if find(x) != find(y):\n",
    "                father[find(x)] = find(y) \n",
    "                return True\n",
    "                \n",
    "                \n",
    "\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(i+1,len(strs)):\n",
    "                if conclude(i,j):\n",
    "                    if union(i, j):\n",
    "                        stack-= 1\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        def issimilar(str1, str2):\n",
    "            n = len(str1)\n",
    "            flag = 0\n",
    "            for c1, c2 in zip(str1, str2):\n",
    "                if c1 != c2:\n",
    "                    flag += 1\n",
    "                    if flag > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def find(index):\n",
    "            while parent[index] != index:\n",
    "                index = parent[index]\n",
    "            return index\n",
    "\n",
    "        # def union(ind1, ind2):\n",
    "        #     parent[ind1] = find(ind2)\n",
    "        \n",
    "        ans = 0\n",
    "        list_len = len(strs)\n",
    "        parent = list(range(list_len))\n",
    "        for i in range(list_len - 1):\n",
    "            for j in range(i+1, list_len):\n",
    "                fi, fj = find(i), find(j)\n",
    "                if fi == fj:\n",
    "                    continue\n",
    "                if issimilar(strs[i], strs[j]):\n",
    "                    parent[fi] = fj\n",
    "        for i in range(list_len):\n",
    "            if parent[i] == i:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        def check(s: str, t: str) -> bool:\n",
    "            diff = []\n",
    "            for i, (x, y) in enumerate(zip(s, t)):\n",
    "                if x != y:\n",
    "                    diff.append(i)\n",
    "                    if len(diff) > 2:\n",
    "                        return False\n",
    "            if not diff:\n",
    "                return True\n",
    "            i, j = diff\n",
    "            return s[i] == t[j] and s[j] == t[i]\n",
    "\n",
    "        n = len(strs)\n",
    "        fa = list(range(n))\n",
    "\n",
    "        def find(x: int) -> int:\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if check(strs[i], strs[j]):\n",
    "                    fa[find(i)] = find(j)\n",
    "        for i in range(n):\n",
    "            fa[i] = find(fa[i])\n",
    "        return len(set(fa))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "'''\n",
    "--- 从此处复制 ---\n",
    "'''\n",
    "class IdentityDefaultDict(defaultdict):\n",
    "    '''\n",
    "    该类用于处理并查集初始化的恒等映射\n",
    "    '''\n",
    "    def __missing__(self, key):\n",
    "        return key\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n=None):\n",
    "        self.parent = IdentityDefaultDict()\n",
    "        if n: self.parent = list(range(n))\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y: self.parent[x] = y\n",
    "    def get_group_count(self):\n",
    "        return len(set(self.find(x) for x in self.parent))\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        \n",
    "        n = len(strs)\n",
    "        uf = UnionFind(n)\n",
    "        for i in range(n):\n",
    "            x = strs[i]\n",
    "            for j in range(i+1, n):\n",
    "                y = strs[j]\n",
    "                if x == y:\n",
    "                    uf.merge(i, j) \n",
    "                    continue\n",
    "                if sum(int(a != b) for a, b in zip(x, y)) == 2:\n",
    "                    uf.merge(i, j)\n",
    "        return uf.get_group_count()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        N = len(strs)\n",
    "\n",
    "        # 判断是否相似\n",
    "        def check(s1, s2):\n",
    "            num = 0\n",
    "            for c1, c2 in zip(s1, s2):\n",
    "                num += c1 != c2\n",
    "                if num == 3:\n",
    "                    return False\n",
    "            return num != 1\n",
    "\n",
    "        # 查并集\n",
    "        l_p = list(range(N))\n",
    "\n",
    "        def find(i):\n",
    "            p = l_p[i]\n",
    "            while p != l_p[p]:\n",
    "                p = l_p[p]\n",
    "            return p\n",
    "\n",
    "        def add(i, j):\n",
    "            l_p[find(i)] = find(j)\n",
    "\n",
    "        # 循环判断是否相似\n",
    "        for i, s1 in enumerate(strs):\n",
    "            for j in range(i + 1, N):\n",
    "                if check(s1, strs[j]):\n",
    "                    add(i, j)\n",
    "\n",
    "        # 多少个相似组就是查并集有多少块\n",
    "        ret = {find(i) for i in range(N)}\n",
    "        return len(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        stack = len(strs)\n",
    "        def conclude(x, y):         \n",
    "            count = 0         \n",
    "            if count <=2:\n",
    "                for i in range(len(strs[x])):                              \n",
    "                    if strs[x][i] != strs[y][i]:\n",
    "                        count +=1\n",
    "            return count <=2\n",
    "\n",
    "        father = []\n",
    "        for i in range(len(strs)):\n",
    "            father.append(i)\n",
    "        \n",
    "        def find(x):\n",
    "            if x != father[x]:\n",
    "                father[x] = find(father[x])\n",
    "            return  father[x]\n",
    "        \n",
    "\n",
    "        def union(x, y):\n",
    "            if find(x) != find(y):\n",
    "                father[find(x)] = find(y) \n",
    "                return True\n",
    "                \n",
    "                \n",
    "\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(i+1,len(strs)):\n",
    "                if conclude(i,j):\n",
    "                    if union(i, j):\n",
    "                        stack-= 1\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        #思路： 并查集，字符串相当于点，相似对应于是否存在边，转换为求图中连通分量的个数\n",
    "        n = len(strs)\n",
    "        f = list(range(n)) # 初始化， 第i个str和自身(i-th str)相似\n",
    "\n",
    "        def find(x: int) -> int:\n",
    "            #对于第x个str， 以递归的方式找到与其相似的且只与自身相似的str的idx\n",
    "            if f[x] == x:\n",
    "                return x\n",
    "            \n",
    "            f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        def check(a: str, b: str) -> bool:\n",
    "            #判断字符串是否相似\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                fi, fj = find(i), find(j) # 递归找到i-th,j-th strs所属的只和自身相似的str的idx\n",
    "                # 相等则跳过，避免重复比较\n",
    "                if fi == fj:\n",
    "                    continue\n",
    "                if check(strs[i], strs[j]):\n",
    "                    f[fi] = fj\n",
    "        \n",
    "        ret = sum(1 for i in range(n) if f[i] == i)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        N = len(strs)\n",
    "\n",
    "        # 判断是否相似\n",
    "        def check(s1, s2):\n",
    "            num = 0\n",
    "            for c1, c2 in zip(s1, s2):\n",
    "                num += c1 != c2\n",
    "                if num == 3:\n",
    "                    return False\n",
    "            return num != 1\n",
    "\n",
    "        # 查并集\n",
    "        l_p = list(range(N))\n",
    "\n",
    "        def find(i):\n",
    "            p = l_p[i]\n",
    "            while p != l_p[p]:\n",
    "                p = l_p[p]\n",
    "            return p\n",
    "\n",
    "        def add(i, j):\n",
    "            l_p[find(i)] = find(j)\n",
    "\n",
    "        # 循环判断是否相似\n",
    "        for i, s1 in enumerate(strs):\n",
    "            for j in range(i + 1, N):\n",
    "                if check(s1, strs[j]):\n",
    "                    add(i, j)\n",
    "\n",
    "        # 多少个相似组就是查并集有多少块\n",
    "        ret = [i for i in range(N) if l_p[i] == i]\n",
    "        return len(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        self.len = len(strs)\n",
    "        self.fathers = []\n",
    "        for i in range(self.len):\n",
    "            self.fathers.append(i)\n",
    "        self.res = self.len\n",
    "\n",
    "        for i in range(self.len):\n",
    "            for j in range(i+1, self.len):\n",
    "                if self.issimilar(strs[i], strs[j]) and self.union(i, j):\n",
    "                    self.res-=1\n",
    "        return (self.res)\n",
    "\n",
    "\n",
    "    def issimilar(self, str1, str2):\n",
    "        count = 0\n",
    "        for i in range(len(str1)):\n",
    "            if str1[i]!=str2[i]:\n",
    "                count+=1\n",
    "        return count<=2\n",
    "\n",
    "\n",
    "    def union(self, i, j):\n",
    "        father_i = self.findfather(i)\n",
    "        father_j = self.findfather(j)\n",
    "        if father_i!=father_j:\n",
    "            self.fathers[father_i] = father_j\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "\n",
    "    def findfather(self, idx):\n",
    "        if self.fathers[idx]!=idx:\n",
    "            self.fathers[idx] = self.findfather(self.fathers[idx])\n",
    "        return self.fathers[idx]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        def issimilar(str1, str2):\n",
    "            n = len(str1)\n",
    "            flag = 0\n",
    "            for c1, c2 in zip(str1, str2):\n",
    "                if c1 != c2:\n",
    "                    flag += 1\n",
    "                    if flag > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def find(index):\n",
    "            while parent[index] != index:\n",
    "                index = parent[index]\n",
    "            return index\n",
    "\n",
    "        def union(ind1, ind2):\n",
    "            parent[ind1] = find(ind2)\n",
    "        \n",
    "        ans = 0\n",
    "        list_len = len(strs)\n",
    "        parent = list(range(list_len))\n",
    "        for i in range(list_len - 1):\n",
    "            for j in range(i+1, list_len):\n",
    "                fi, fj = find(i), find(j)\n",
    "                if fi == fj:\n",
    "                    continue\n",
    "                if issimilar(strs[i], strs[j]):\n",
    "                    parent[fi] = fj\n",
    "        for i in range(list_len):\n",
    "            if parent[i] == i:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        f = list(range(n))\n",
    "\n",
    "        def find(x: int) -> int:\n",
    "            if f[x] == x:\n",
    "                return x\n",
    "            f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        def check(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                fi, fj = find(i), find(j)\n",
    "                if fi == fj:\n",
    "                    continue\n",
    "                if check(strs[i], strs[j]):\n",
    "                    f[fi] = fj\n",
    "        \n",
    "        ret = sum(1 for i in range(n) if f[i] == i)\n",
    "        return ret\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/H6lPxb/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        f = list(range(n))\n",
    "\n",
    "        def find(x: int) -> int:\n",
    "            if f[x] == x:\n",
    "                return x\n",
    "            f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        def check(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                fi, fj = find(i), find(j)\n",
    "                if fi == fj:\n",
    "                    continue\n",
    "                if check(strs[i], strs[j]):\n",
    "                    f[fi] = fj\n",
    "        \n",
    "        ret = sum(1 for i in range(n) if f[i] == i)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        stack = len(strs)\n",
    "        def conclude(x, y):         \n",
    "            count = 0         \n",
    "            if count <=2:\n",
    "                for i in range(len(strs[x])):                              \n",
    "                    if strs[x][i] != strs[y][i]:\n",
    "                        count +=1\n",
    "            return count <=2\n",
    "\n",
    "        father = []\n",
    "        for i in range(len(strs)):\n",
    "            father.append(i)\n",
    "        \n",
    "        def find(x):\n",
    "            if x != father[x]:\n",
    "                father[x] = find(father[x])\n",
    "            return  father[x]\n",
    "        \n",
    "\n",
    "        def union(x, y):\n",
    "            if find(x) != find(y):\n",
    "                father[find(x)] = find(y) \n",
    "                return True\n",
    "                \n",
    "                \n",
    "\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(i+1,len(strs)):\n",
    "                if conclude(i,j):\n",
    "                    if union(i, j):\n",
    "                        stack-= 1\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        #思路： 并查集，字符串相当于点，相似对应于是否存在边，转换为求图中连通分量的个数\n",
    "        n = len(strs)\n",
    "        f = list(range(n)) # 初始化， 第i个str和自身(i-th str)相似\n",
    "\n",
    "        def find(x: int) -> int:\n",
    "            #对于第x个str， 以递归的方式找到与其相似的且只与自身相似的str的idx\n",
    "            if f[x] == x:\n",
    "                return x\n",
    "            f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        def check(a: str, b: str) -> bool:\n",
    "            #判断字符串是否相似\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                fi, fj = find(i), find(j) # 递归找到i-th,j-th strs所属的只和自身相似的str的idx\n",
    "                # 相等则跳过，避免重复比较\n",
    "                if fi == fj:\n",
    "                    continue\n",
    "                if check(strs[i], strs[j]):\n",
    "                    f[fi] = fj\n",
    "        \n",
    "        ret = sum(1 for i in range(n) if f[i] == i)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        parent = list(range(n))\n",
    "\n",
    "        def find_root(x):\n",
    "            if parent[x] == x:\n",
    "                return x\n",
    "            parent[x] = find_root(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def is_connected(a, b):\n",
    "            if a == b:\n",
    "                return True\n",
    "            if len(a) != len(b):\n",
    "                return False\n",
    "            diff_chars = ['', '']\n",
    "            for cha, chb in zip(a, b):\n",
    "                if cha != chb:\n",
    "                    diff_chars[0] += cha\n",
    "                    diff_chars[1] += chb\n",
    "            if (len(diff_chars[0]) != 2) or (diff_chars[0] != diff_chars[1][::-1]):\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                root_i, root_j = find_root(i), find_root(j)\n",
    "                if root_i == root_j:\n",
    "                    continue\n",
    "                if is_connected(strs[i], strs[j]):\n",
    "                    parent[root_j] = root_i\n",
    "\n",
    "        num = sum(parent[i] == i for i in range(n))\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        def isSimilar(str1, str2):\n",
    "            unlikeNum = len(str1)\n",
    "            for i in range(unlikeNum):\n",
    "                if str1[i] == str2[i]:\n",
    "                    unlikeNum = unlikeNum - 1\n",
    "            return unlikeNum <= 2\n",
    "\n",
    "        groups = []\n",
    "        while len(strs) > 0:\n",
    "            aGroup = [strs[0]]\n",
    "            strs.remove(strs[0])\n",
    "            groupIndex = 0\n",
    "            while groupIndex < len(aGroup):\n",
    "                strIndex = 0\n",
    "                while strIndex < len(strs):\n",
    "                    if isSimilar(aGroup[groupIndex], strs[strIndex]):\n",
    "                        aGroup.append(strs[strIndex])\n",
    "                        strs.remove(strs[strIndex])\n",
    "                    else:\n",
    "                        strIndex = strIndex + 1\n",
    "                groupIndex = groupIndex + 1\n",
    "            groups.append(aGroup)\n",
    "        return len(groups)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "        self.size = {}\n",
    "        self.cnt = 0\n",
    "\n",
    "    def add(self, x: str):\n",
    "        self.parent[x] = x\n",
    "        self.size[x] = 1\n",
    "        self.cnt += 1\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            return self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, p, q):\n",
    "        if self.connected(p, q): return\n",
    "        # 小的树挂到大的树上， 使树尽量平衡\n",
    "        leader_p = self.find(p)\n",
    "        leader_q = self.find(q)\n",
    "        if self.size[leader_p] < self.size[leader_q]:\n",
    "            self.parent[leader_p] = leader_q\n",
    "            self.size[leader_q] += self.size[leader_p]\n",
    "        else:\n",
    "            self.parent[leader_q] = leader_p\n",
    "            self.size[leader_p] += self.size[leader_q]\n",
    "        self.cnt -= 1\n",
    "\n",
    "\n",
    "    def connected(self, p, q):\n",
    "        return self.find(p) == self.find(q)\n",
    "\n",
    "class Solution:\n",
    "    def isValid(self, a:str, b:str):\n",
    "        if len(a) != len(b):\n",
    "            return False\n",
    "        diff = []\n",
    "        for i in range(len(a)):\n",
    "            if a[i] != b[i]:\n",
    "                diff.append((a[i], b[i]))\n",
    "        \n",
    "        if not diff:\n",
    "            return  True\n",
    "        if len(diff) == 2 and diff[0][0] == diff[1][1] and diff[0][1] == diff[1][0]:\n",
    "            return True\n",
    "        return False\n",
    "    \n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs_ = []\n",
    "        seen = set()\n",
    "        for s in strs:\n",
    "            if s not in seen:\n",
    "                strs_.append(s)\n",
    "                seen.add(s)\n",
    "        \n",
    "        uf = UF()\n",
    "        for s in strs_:\n",
    "            uf.add(s)\n",
    "        \n",
    "        for right in range(len(strs_)):\n",
    "            for left in range(right):\n",
    "                if self.isValid(strs_[left], strs_[right]):\n",
    "                    uf.union(strs_[left], strs_[right])\n",
    "            \n",
    "                    \n",
    "        return uf.cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "\n",
    "        def check(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        # 优化后的代码\n",
    "\n",
    "        dis1 = [0] * m\n",
    "        for i in range(m):\n",
    "            dis1[i] = sum(1 for j in range(n) if strs[0][j] != strs[i][j])\n",
    "            if dis1[i] == 2:\n",
    "                merge(0, i)\n",
    "\n",
    "        index = [x[1] for x in sorted((dis1[i], i) for i in range(1, m))]\n",
    "        p = 1\n",
    "        for i in range(0, m - 1):\n",
    "            x = strs[index[i]]\n",
    "            d = dis1[index[i]]\n",
    "            while p < m - 1 and dis1[index[p]] - d <= 2:\n",
    "                p += 1\n",
    "            for j in range(i + 1, p):\n",
    "                if check(strs[index[j]], x):\n",
    "                    merge(index[i], index[j])\n",
    "\n",
    "        # 优化前的代码\n",
    "\n",
    "        # for i in range(0, m):\n",
    "        #     for j in range(i + 1, m):\n",
    "        #         if find(i) != find(j) and check(strs[i], strs[j]):\n",
    "        #             merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    stack = 0\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        global stack\n",
    "        stack = len(strs)\n",
    "        def conclude(x, y):         \n",
    "            count = 0         \n",
    "            if count <=2:\n",
    "                for i in range(len(strs[x])):                              \n",
    "                    if strs[x][i] != strs[y][i]:\n",
    "                        count +=1\n",
    "            return count <=2\n",
    "\n",
    "        father = []\n",
    "        for i in range(len(strs)):\n",
    "            father.append(i)\n",
    "        \n",
    "        def find(x):\n",
    "            if x != father[x]:\n",
    "                father[x] = find(father[x])\n",
    "            return father[x]\n",
    "        \n",
    "\n",
    "        def union(x, y):\n",
    "            if find(x) != find(y):\n",
    "                father[find(x)] = find(y)\n",
    "                global stack \n",
    "                stack -= 1\n",
    "                \n",
    "                \n",
    "\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(i+1,len(strs)):\n",
    "                if conclude(i,j):\n",
    "                    union(i, j)\n",
    "\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "\n",
    "        def check(x, y):\n",
    "            r = 0\n",
    "            for i in range(n):\n",
    "                if x[i] != y[i]:\n",
    "                    r += 1\n",
    "                if r > 2:\n",
    "                    return False\n",
    "            return r == 2\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        dis1 = [0] * m\n",
    "        for i in range(m):\n",
    "            dis1[i] = sum(1 for j in range(n) if strs[0][j] != strs[i][j])\n",
    "            if dis1[i] == 2:\n",
    "                merge(0, i)\n",
    "\n",
    "        # index = [x[1] for x in sorted((dis1[i], i) for i in range(1, m))]\n",
    "        # p = 1\n",
    "        # for i in range(0, m - 1):\n",
    "        #     x = strs[index[i]]\n",
    "        #     d = dis1[index[i]]\n",
    "        #     while p < m - 1 and dis1[index[p]] - d <= 2:\n",
    "        #         p += 1\n",
    "        #     for j in range(i + 1, p):\n",
    "        #         if check(strs[index[j]], x):\n",
    "        #             merge(index[i], index[j])\n",
    "\n",
    "        for i in range(0, m):\n",
    "            for j in range(i + 1, m):\n",
    "                if find(i) != find(j) and check(strs[i], strs[j]):\n",
    "                    merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        self.father = [0]*301\n",
    "        self.sets = 0\n",
    "        def build(n):\n",
    "            for i in range(n):\n",
    "                self.father[i] = i\n",
    "            self.sets = n\n",
    "        def find(i):\n",
    "            if i!=self.father[i]:\n",
    "                self.father[i] = find(self.father[i])\n",
    "            return self.father[i]\n",
    "        def union(x,y):\n",
    "            fx = find(x)\n",
    "            fy = find(y)\n",
    "            if fx!=fy:\n",
    "                self.father[fx] = fy\n",
    "                self.sets -= 1\n",
    "        n = len(strs)\n",
    "        m = len(strs[0])\n",
    "        build(n)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if find(i)!=find(j):\n",
    "                    diff = 0\n",
    "                    for k in range(m):\n",
    "                        if diff>3:\n",
    "                            break\n",
    "                        if strs[i][k]!=strs[j][k]:\n",
    "                            diff += 1\n",
    "                    if diff==0 or diff==2:\n",
    "                        union(i,j)\n",
    "        return self.sets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "\n",
    "        def check_slow(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def check(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for i in range(len(a)):\n",
    "                if a[i] != b[i]:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        for i in range(0, m):\n",
    "            for j in range(i + 1, m):\n",
    "                if find(i) != find(j) and check(strs[i], strs[j]):\n",
    "                    merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "\n",
    "        def check_slow(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        def check(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for i in range(len(a)):\n",
    "                if a[i] != b[i]:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        for i in range(0, m):\n",
    "            for j in range(i + 1, m):\n",
    "                if find(i) != find(j) and check(strs[i], strs[j]):\n",
    "                    merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                num_diffs = 0\n",
    "                for k in range(len(strs[i])):\n",
    "                    if strs[i][k] != strs[j][k]:\n",
    "                        num_diffs += 1\n",
    "                        if num_diffs > 2:\n",
    "                            break\n",
    "                if num_diffs == 0 or num_diffs == 2:\n",
    "                    g[i].append(j)\n",
    "                    g[j].append(i)\n",
    "        num_groups = 0\n",
    "        visited = [False] * n\n",
    "        for i in range(n):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            num_groups += 1\n",
    "            q, head = [i], -1\n",
    "            visited[i] = True\n",
    "            while head < len(q) - 1:\n",
    "                head += 1\n",
    "                u = q[head]\n",
    "                for v in g[u]:\n",
    "                    if not visited[v]:\n",
    "                        q.append(v)\n",
    "                        visited[v] = True\n",
    "        return num_groups"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "\n",
    "        def check(x, y):\n",
    "            r = 0\n",
    "            for i in range(n):\n",
    "                if x[i] != y[i]:\n",
    "                    r += 1\n",
    "                if r > 2:\n",
    "                    return False\n",
    "            return r == 2\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        dis1 = [0] * m\n",
    "        for i in range(m):\n",
    "            dis1[i] = sum(1 for j in range(n) if strs[0][j] != strs[i][j])\n",
    "            if dis1[i] == 2:\n",
    "                merge(0, i)\n",
    "\n",
    "        index = [x[1] for x in sorted((dis1[i], i) for i in range(1, m))]\n",
    "        p = 1\n",
    "        for i in range(0, m - 1):\n",
    "            x = strs[index[i]]\n",
    "            d = dis1[index[i]]\n",
    "            while p < m - 1 and dis1[index[p]] - d <= 2:\n",
    "                p += 1\n",
    "            for j in range(i + 1, p):\n",
    "                if check(strs[index[j]], x):\n",
    "                    merge(index[i], index[j])\n",
    "\n",
    "        # for i in range(0, m):\n",
    "        #     for j in range(i + 1, m):\n",
    "        #         if find(i) != find(j) and check(strs[i], strs[j]):\n",
    "        #             merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        method = 'leetcode'\n",
    "        if method == 'leetcode':\n",
    "            #并查集\n",
    "            n = len(strs)\n",
    "            f = list(range(n))\n",
    "\n",
    "            def find(x):\n",
    "                if f[x] == x:\n",
    "                    return x\n",
    "                f[x] = find(f[x])\n",
    "                return f[x]\n",
    "\n",
    "            def check(a, b):\n",
    "                num = 0\n",
    "                for ac, bc in zip(a, b):\n",
    "                    if ac != bc:\n",
    "                        num += 1\n",
    "                        if num > 2:\n",
    "                            return False\n",
    "                return True\n",
    "            \n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    f1, f2 = find(i), find(j)\n",
    "                    if f1 == f2:\n",
    "                        continue\n",
    "                    else:\n",
    "                        if check(strs[i], strs[j]):\n",
    "                            f[f1] = f2\n",
    "            res = sum(1 for i in range(n) if f[i] == i)\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        stack = len(strs)\n",
    "        def conclude(x, y):         \n",
    "            count = 0         \n",
    "            if count <=2:\n",
    "                for i in range(len(strs[x])):                              \n",
    "                    if strs[x][i] != strs[y][i]:\n",
    "                        count +=1\n",
    "            return count <=2\n",
    "\n",
    "        father = []\n",
    "        for i in range(len(strs)):\n",
    "            father.append(i)\n",
    "        \n",
    "        def find(x):\n",
    "            if x != father[x]:\n",
    "                father[x] = find(father[x])\n",
    "            return  father[x]\n",
    "        \n",
    "\n",
    "        def union(x, y):\n",
    "            if find(x) != find(y):\n",
    "                father[find(x)] = find(y) \n",
    "                return True\n",
    "                \n",
    "                \n",
    "\n",
    "        for i in range(len(strs)):\n",
    "            for j in range(i+1,len(strs)):\n",
    "                if conclude(i,j):\n",
    "                    if union(i, j):\n",
    "                        stack-= 1\n",
    "        return stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n, m = len(strs), len(strs[0])\n",
    "        fa = list(range(n))\n",
    "        def find(x: int) -> int:\n",
    "            cur = x\n",
    "            while x != fa[x]:\n",
    "                x = fa[x]\n",
    "            while fa[cur] != x:\n",
    "                fa[cur], cur = x, fa[cur]\n",
    "            return x\n",
    "        \n",
    "        def check(s: str, t: str) -> bool:\n",
    "            return sum(a != b for a, b in zip(s, t)) <= 2\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                fi, fj = find(i), find(j)\n",
    "                if fi != fj and check(strs[i], strs[j]):\n",
    "                    fa[fi] = fj\n",
    "        \n",
    "        return sum(find(i) == i for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        f = list(range(n))\n",
    "\n",
    "        def find(x):\n",
    "            if f[x] == x:\n",
    "                return x\n",
    "            f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        def check(a, b):\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True \n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                fi, fj = find(i), find(j)\n",
    "                if fi == fj:\n",
    "                    continue\n",
    "                if check(strs[i], strs[j]):\n",
    "                    f[fj] = fi \n",
    "\n",
    "        ret = sum(1 for i in range(n) if f[i] == i)\n",
    "\n",
    "        return ret \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        #思路： 并查集，字符串相当于点，相似对应于是否存在边，转换为求图中连通分量的个数\n",
    "        n = len(strs)\n",
    "        f = list(range(n)) # 初始化， 第i个str和自身(i-th str)相似\n",
    "\n",
    "        def find(x: int) -> int:\n",
    "            #对于第x个str， 以递归的方式找到与其相似的且只与自身相似的str的idx\n",
    "            if f[x] == x:\n",
    "                return x\n",
    "            else:\n",
    "                f[x] = find(f[x])\n",
    "                return f[x]\n",
    "        \n",
    "        def check(a: str, b: str) -> bool:\n",
    "            #判断字符串是否相似\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                fi, fj = find(i), find(j) # 递归找到i-th,j-th strs所属的只和自身相似的str的idx\n",
    "                # 相等则跳过，避免重复比较\n",
    "                if fi == fj:\n",
    "                    continue\n",
    "                if check(strs[i], strs[j]):\n",
    "                    f[fi] = fj\n",
    "        \n",
    "        ret = sum(1 for i in range(n) if f[i] == i)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "\n",
    "        def check(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        # 优化后的代码\n",
    "\n",
    "        dis1 = [0] * m\n",
    "        for i in range(m):\n",
    "            dis1[i] = sum(1 for j in range(n) if strs[0][j] != strs[i][j])\n",
    "            if dis1[i] == 2:\n",
    "                merge(0, i)\n",
    "\n",
    "        index = [x[1] for x in sorted((dis1[i], i) for i in range(1, m))]\n",
    "        p = 1\n",
    "        for i in range(0, m - 1):\n",
    "            x = strs[index[i]]\n",
    "            d = dis1[index[i]]\n",
    "            while p < m - 1 and dis1[index[p]] - d <= 2:\n",
    "                p += 1\n",
    "            for j in range(i + 1, p):\n",
    "                if check(strs[index[j]], x):\n",
    "                    merge(index[i], index[j])\n",
    "\n",
    "        # 优化前的代码\n",
    "\n",
    "        # for i in range(0, m):\n",
    "        #     for j in range(i + 1, m):\n",
    "        #         if find(i) != find(j) and check(strs[i], strs[j]):\n",
    "        #             merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        size, p, rank = 0, [], []\n",
    "        def find(x) : \n",
    "            return x if x == p[x]  else find(p[x]) \n",
    "\n",
    "        def union(x, y):\n",
    "            rootX, rootY = find(x), find(y)\n",
    "            if rootX == rootY: \n",
    "                return\n",
    "            if rank[rootX] < rank[rootY]:\n",
    "                p[rootX] = rootY\n",
    "            elif rank[rootX] > rank[rootY]:\n",
    "                p[rootY] = rootX\n",
    "            else:\n",
    "                p[rootX] = rootY\n",
    "                rank[rootY] += 1\n",
    "            \n",
    "        \n",
    "        def isSmilar(s1, s2):\n",
    "            cnt = 0\n",
    "            for i in range(size):\n",
    "                if s1[i] != s2[i]:\n",
    "                    if cnt == 2:\n",
    "                        return False\n",
    "                    cnt += 1\n",
    "            return cnt == 2 or cnt == 0\n",
    "        \n",
    "        size = len(strs[0])\n",
    "        n = len(strs)\n",
    "        p = [0] * n\n",
    "        for i in range(n):\n",
    "            p[i] = i\n",
    "        \n",
    "        rank = [1] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n, 1):\n",
    "                x, y = find(i), find(j)\n",
    "                p[i], p[j] = x, y\n",
    "                if x != y and isSmilar(strs[i], strs[j]) :\n",
    "                    p[x] = y\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if p[i] == i:\n",
    "                ans += 1\n",
    "            \n",
    "        \n",
    "        return ans\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "\n",
    "        def check(x, y):\n",
    "            r = 0\n",
    "            for i in range(n):\n",
    "                if x[i] != y[i]:\n",
    "                    r += 1\n",
    "                if r > 2:\n",
    "                    return False\n",
    "            return r == 2\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        dis1 = [0] * m\n",
    "        for i in range(m):\n",
    "            dis1[i] = sum(1 for j in range(n) if strs[0][j] != strs[i][j])\n",
    "            if dis1[i] == 2:\n",
    "                merge(0, i)\n",
    "\n",
    "        # index = [x[1] for x in sorted((dis1[i], i) for i in range(1, m))]\n",
    "        # p = 1\n",
    "        # for i in range(0, m - 1):\n",
    "        #     x = strs[index[i]]\n",
    "        #     d = dis1[index[i]]\n",
    "        #     while p < m - 1 and dis1[index[p]] - d <= 2:\n",
    "        #         p += 1\n",
    "        #     for j in range(i + 1, p):\n",
    "        #         if check(strs[index[j]], x):\n",
    "        #             merge(index[i], index[j])\n",
    "\n",
    "        for i in range(0, m):\n",
    "            for j in range(i + 1, m):\n",
    "                if find(i) != find(j) and check(strs[i], strs[j]):\n",
    "                    merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "\n",
    "        def check(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        for i in range(0, m):\n",
    "            for j in range(i + 1, m):\n",
    "                if find(i) != find(j) and check(strs[i], strs[j]):\n",
    "                    merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        fa = list(range(n))\n",
    "        def find(x):\n",
    "            if x == fa[x]:\n",
    "                return x\n",
    "            fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def check(a, b):\n",
    "            flag = 0\n",
    "            for i, j in zip(a, b):\n",
    "                if i != j:\n",
    "                    flag += 1\n",
    "                    if flag > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                fi, fj = find(i), find(j)\n",
    "                if fi == fj:\n",
    "                    continue\n",
    "                if check(strs[i], strs[j]):\n",
    "                    fa[fj] = fi\n",
    "        \n",
    "        return sum(1 for i in range(n) if fa[i] == i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs) \n",
    "        def check(word1,word2): \n",
    "            ct=0 \n",
    "            for i in range(len(word1)): \n",
    "                if word1[i] != word2[i]: \n",
    "                    ct+=1 \n",
    "                    if ct>2: \n",
    "                        return False \n",
    "            return True  \n",
    "        def dfs(i):\n",
    "            vis[i]=True\n",
    "            for j in range(n):\n",
    "                if vis[j]==False and check(strs[i],strs[j]):\n",
    "                    dfs(j)\n",
    "    \n",
    "        vis = [False]*n\n",
    "        ct=0\n",
    "        for i in range(n):\n",
    "            if vis[i]: continue\n",
    "            dfs(i)\n",
    "            ct+=1                \n",
    "        return ct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        parents = list(range(n))\n",
    "\n",
    "        def find(idx):\n",
    "            nonlocal parents\n",
    "            if parents[idx] != idx:\n",
    "                parents[idx] = find(parents[idx])\n",
    "            return parents[idx]\n",
    "        \n",
    "        def check(idx1, idx2):\n",
    "            cnt = 0 \n",
    "            for ch1, ch2 in zip(idx1, idx2):\n",
    "                if ch1 != ch2:\n",
    "                    cnt += 1\n",
    "                    if cnt > 2:\n",
    "                        return False \n",
    "            return True \n",
    "        \n",
    "        def union(idx1, idx2):\n",
    "            nonlocal parents\n",
    "            parents[find(idx1)] = find(idx2)\n",
    "        \n",
    "        res = n \n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                parenti, parentj = find(i), find(j)\n",
    "                if parenti == parentj:\n",
    "                    continue \n",
    "                if check(strs[i], strs[j]):\n",
    "                    union(i, j)\n",
    "                    res -= 1\n",
    "        return res \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "        def check(x, y):\n",
    "            return sum(1 for i in range(n) if x[i] != y[i])\n",
    "        rec = [[0] * n for i in range(n)]\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        dis1 = [0] * m\n",
    "        for i in range(m):\n",
    "            dis1[i] = check(strs[0], strs[i])\n",
    "            if dis1[i] == 2:\n",
    "                merge(0, i)\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(i + 1, m):\n",
    "                if find(i) != find(j) and abs(dis1[i] - dis1[j]) <= 2:\n",
    "                    if check(strs[i], strs[j]) == 2:\n",
    "                        merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "\n",
    "        def check(x, y):\n",
    "            r = 0\n",
    "            for i in range(n):\n",
    "                if x[i] != y[i]:\n",
    "                    r += 1\n",
    "                if r > 2:\n",
    "                    return False\n",
    "            return r == 2\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        dis1 = [0] * m\n",
    "        for i in range(m):\n",
    "            dis1[i] = sum(1 for j in range(n) if strs[0][j] != strs[i][j])\n",
    "            if dis1[i] == 2:\n",
    "                merge(0, i)\n",
    "\n",
    "        # index = [x[1] for x in sorted((dis1[i], i) for i in range(1, m))]\n",
    "        # p = 1\n",
    "        # for i in range(0, m - 1):\n",
    "        #     x = strs[index[i]]\n",
    "        #     d = dis1[index[i]]\n",
    "        #     while p < m - 1 and dis1[index[p]] - d <= 2:\n",
    "        #         p += 1\n",
    "        #     for j in range(i + 1, p):\n",
    "        #         if check(strs[index[j]], x):\n",
    "        #             merge(index[i], index[j])\n",
    "\n",
    "        for i in range(0, m):\n",
    "            for j in range(i + 1, m):\n",
    "                if find(i) != find(j) and check(strs[i], strs[j]):\n",
    "                    merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        def check(wordx: str, wordy: str) -> bool:\n",
    "            wn = len(wordx)\n",
    "            cnt = 0\n",
    "            for i in range(wn):\n",
    "                if wordx[i] != wordy[i]:\n",
    "                    cnt += 1\n",
    "                    if cnt > 2:\n",
    "                        return False\n",
    "            return cnt == 0 or cnt == 2\n",
    "        \n",
    "        def bfs(sx: int) -> bool:\n",
    "            q = collections.deque()\n",
    "            q.append(sx)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                for y in range(n):\n",
    "                    if visited[y] == False and check(strs[x], strs[y]) == True:\n",
    "                        visited[y] = True\n",
    "                        q.append(y)\n",
    "        \n",
    "        n = len(strs)\n",
    "        visited = [False for _ in range(n)]\n",
    "        cnt = 0\n",
    "        for x in range(n):\n",
    "            if visited[x] == False:\n",
    "                visited[x] = True\n",
    "                bfs(x)\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        child = [[] for _ in range(n)]\n",
    "\n",
    "        def isgood(s1, s2):\n",
    "            num = 0\n",
    "            for a, b in zip(s1, s2):\n",
    "                if a != b:\n",
    "                    num += 1\n",
    "                    if num == 3:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if isgood(strs[i], strs[j]):\n",
    "                    child[i].append(j)\n",
    "                    child[j].append(i)\n",
    "        \n",
    "        finded = [1 for _ in range(n)]\n",
    "\n",
    "        def dfs(num):\n",
    "            if not finded[num]:\n",
    "                return 0\n",
    "            finded[num] = 0\n",
    "            for c in child[num]:\n",
    "                if finded[c]:\n",
    "                    dfs(c)\n",
    "            return 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0] * n\n",
    "    \n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x: int, y: int) -> bool:\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        \n",
    "        if rootX == rootY:\n",
    "            return False\n",
    "        \n",
    "        if self.rank[rootX] > self.rank[rootY]:\n",
    "            self.parent[rootY] = rootX\n",
    "        elif self.rank[rootX] < self.rank[rootY]:\n",
    "            self.parent[rootX] = rootY\n",
    "        else:\n",
    "            self.parent[rootY] = rootX\n",
    "            self.rank[rootX] += 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        if not strs: return 0\n",
    "        \n",
    "        def isSimilar(str1: str, str2: str) -> bool:\n",
    "            diff = 0\n",
    "            for i in range(len(str1)):\n",
    "                if str1[i] != str2[i]:\n",
    "                    diff += 1\n",
    "                if diff > 2:\n",
    "                    return False\n",
    "            return diff == 0 or diff == 2\n",
    "        \n",
    "        n = len(strs)\n",
    "        uf = UnionFind(n)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if isSimilar(strs[i], strs[j]):\n",
    "                    uf.union(i, j)\n",
    "        \n",
    "        groupCount = set()\n",
    "        for i in range(n):\n",
    "            groupCount.add(uf.find(i))\n",
    "        \n",
    "        return len(groupCount)\n",
    "\n",
    "# 测试\n",
    "s = Solution()\n",
    "strs = [\"tars\", \"rats\", \"arts\", \"star\"]\n",
    "print(s.numSimilarGroups(strs))  # 输出：2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        f = list(range(n))\n",
    "\n",
    "        def find(x: int) -> int:\n",
    "            if f[x] == x:\n",
    "                return x\n",
    "            f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        def check(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                fi, fj = find(i), find(j)\n",
    "                if fi == fj:\n",
    "                    continue\n",
    "                if check(strs[i], strs[j]):\n",
    "                    f[fi] = fj\n",
    "        \n",
    "        ret = sum(1 for i in range(n) if f[i] == i)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "\n",
    "        def check(a: str, b: str) -> bool:\n",
    "            num = 0\n",
    "            for ac, bc in zip(a, b):\n",
    "                if ac != bc:\n",
    "                    num += 1\n",
    "                    if num > 2:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        # 优化后的代码\n",
    "\n",
    "        dis1 = [0] * m\n",
    "        for i in range(m):\n",
    "            dis1[i] = sum(1 for j in range(n) if strs[0][j] != strs[i][j])\n",
    "            if dis1[i] == 2:\n",
    "                merge(0, i)\n",
    "\n",
    "        index = [x[1] for x in sorted((dis1[i], i) for i in range(1, m))]\n",
    "        p = 1\n",
    "        for i in range(0, m - 1):\n",
    "            x = strs[index[i]]\n",
    "            d = dis1[index[i]]\n",
    "            while p < m - 1 and dis1[index[p]] - d <= 2:\n",
    "                p += 1\n",
    "            for j in range(i + 1, p):\n",
    "                if check(strs[index[j]], x):\n",
    "                    merge(index[i], index[j])\n",
    "\n",
    "        # 优化前的代码\n",
    "\n",
    "        # for i in range(0, m):\n",
    "        #     for j in range(i + 1, m):\n",
    "        #         if find(i) != find(j) and check(strs[i], strs[j]):\n",
    "        #             merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs) \n",
    "        def check(word1,word2): \n",
    "            ct=0 \n",
    "            for i in range(len(word1)): \n",
    "                if word1[i] != word2[i]: \n",
    "                    ct+=1 \n",
    "                    if ct>2: \n",
    "                        return False \n",
    "            return True\n",
    "  \n",
    "        def dfs(i):\n",
    "            vis[i]=1\n",
    "            for j in range(n):\n",
    "                if vis[j]==0 and check(strs[i],strs[j]):\n",
    "                    dfs(j)\n",
    "    \n",
    "        vis = [0]*n\n",
    "        ct=0\n",
    "        for i in range(n):\n",
    "            if vis[i]==1: continue\n",
    "            dfs(i)\n",
    "            ct+=1\n",
    "                \n",
    "        return ct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        neighbors = defaultdict(list)\n",
    "        n = len(strs)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if self.anag(strs[i],strs[j]):\n",
    "                    neighbors[i].append(j)\n",
    "                    neighbors[j].append(i)\n",
    "        res = 0\n",
    "        visited = [False] * n\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                res += 1\n",
    "                q = deque([i])\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    visited[x] = True\n",
    "                    print(neighbors[x])\n",
    "                    for j in neighbors[x]:\n",
    "                        if not visited[j]:\n",
    "                            q.append(j)\n",
    "                            visited[j] = True\n",
    "        return res\n",
    "\n",
    "    def anag(self, s, t):\n",
    "        n = len(s)\n",
    "        k = 0\n",
    "        one = 0\n",
    "        two = 0\n",
    "        for i in range(n):\n",
    "            if s[i] != t[i]:\n",
    "                if k == 0:\n",
    "                    one = i\n",
    "                    k += 1\n",
    "                elif k == 1:\n",
    "                    two = i\n",
    "                    k += 1\n",
    "                else:\n",
    "                    return False\n",
    "        if k == 1:\n",
    "            return False\n",
    "        elif k == 0:\n",
    "            return True\n",
    "        else:\n",
    "            if s[one] == t[two] and s[two] == t[one]:\n",
    "                return True\n",
    "            else:\n",
    "                return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        child = [[] for _ in range(n)]\n",
    "\n",
    "        def isgood(s1, s2):\n",
    "            num = 0\n",
    "            for a, b in zip(s1, s2):\n",
    "                if a != b:\n",
    "                    num += 1\n",
    "                    if num == 3:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if isgood(strs[i], strs[j]):\n",
    "                    child[i].append(j)\n",
    "                    child[j].append(i)\n",
    "        \n",
    "        finded = [1 for _ in range(n)]\n",
    "\n",
    "        def dfs(num):\n",
    "            if not finded[num]:\n",
    "                return 0\n",
    "            finded[num] = 0\n",
    "            for c in child[num]:\n",
    "                if finded[c]:\n",
    "                    dfs(c)\n",
    "            return 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += dfs(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "        def check(x, y):\n",
    "            return sum(1 for i in range(n) if x[i] != y[i])\n",
    "        rec = [[0] * n for i in range(n)]\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        dis1 = [0] * m\n",
    "        for i in range(m):\n",
    "            dis1[i] = check(strs[0], strs[i])\n",
    "            if dis1[i] == 2:\n",
    "                merge(0, i)\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(i + 1, m):\n",
    "                if abs(dis1[i] - dis1[j]) <= 2 and find(i) != find(j):\n",
    "                    if check(strs[i], strs[j]) == 2:\n",
    "                        merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        n = len(strs) \n",
    "        def check(word1,word2): \n",
    "            ct=0 \n",
    "            for i in range(len(word1)): \n",
    "                if word1[i] != word2[i]: \n",
    "                    ct+=1 \n",
    "                    if ct>2: \n",
    "                        return False \n",
    "            return True  \n",
    "        def dfs(i):\n",
    "            vis[i]=True\n",
    "            for j in range(n):\n",
    "                if not vis[j] and check(strs[i],strs[j]):\n",
    "                    dfs(j)\n",
    "    \n",
    "        vis = [False]*n\n",
    "        ct=0\n",
    "        for i in range(n):\n",
    "            if vis[i]: continue\n",
    "            dfs(i)\n",
    "            ct+=1                \n",
    "        return ct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        cnt = len(strs);ret = 0\n",
    "        visted = [False] * cnt\n",
    "        def is_simlar(s1,s2):#相似判断\n",
    "            diff = 0\n",
    "            for c1,c2 in zip(s1,s2):\n",
    "                if c1 != c2:\n",
    "                    diff+=1\n",
    "                if diff>2:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        def dfs(i):#对比所有可能的相似组\n",
    "            visted[i] = True\n",
    "            for j in range(cnt):\n",
    "                if not visted[j] and is_simlar(strs[i],strs[j]):#没标记过且与当前词语相似\n",
    "                    dfs(j)\n",
    "        for i in range(cnt):\n",
    "            if not visted[i]:\n",
    "                dfs(i)\n",
    "                ret+=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "\n",
    "        def checkNum(x, y):\n",
    "            return sum(1 for i in range(n) if x[i] != y[i])\n",
    "\n",
    "        def check(x, y):\n",
    "            r = 0\n",
    "            for i in range(n):\n",
    "                if x[i] != y[i]:\n",
    "                    r += 1\n",
    "                if r > 2:\n",
    "                    return False\n",
    "            return r == 2\n",
    "\n",
    "        rec = [[0] * n for i in range(n)]\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "        dis1 = [0] * m\n",
    "        for i in range(m):\n",
    "            dis1[i] = checkNum(strs[0], strs[i])\n",
    "            if dis1[i] == 2:\n",
    "                merge(0, i)\n",
    "\n",
    "        index = [x[1] for x in sorted((dis1[i], i) for i in range(1, m))]\n",
    "        p = 1\n",
    "        for i in range(0, m - 1):\n",
    "            x = strs[index[i]]\n",
    "            d = dis1[index[i]]\n",
    "            while p < m - 1 and dis1[index[p]] - d <= 2:\n",
    "                p += 1\n",
    "            for j in range(i + 1, p):\n",
    "                if find(index[i]) != find(index[j]) and check(strs[index[j]], x):\n",
    "                    merge(index[i], index[j])\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSimilarGroups(self, strs: List[str]) -> int:\n",
    "        strs = list(set(strs))\n",
    "        m, n = len(strs), len(strs[0])\n",
    "        def check(x, y):\n",
    "            return sum(1 for i in range(n) if x[i] != y[i])\n",
    "        rec = [[0] * n for i in range(n)]\n",
    "\n",
    "        fa = [i for i in range(m)]\n",
    "\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "\n",
    "        def merge(i, j):\n",
    "            fa[find(i)] = find(j)\n",
    "\n",
    "\n",
    "        for i, x in enumerate(strs):\n",
    "            for j, y in enumerate(strs[i + 1:], start=i + 1):\n",
    "                if check(x, y) == 2:\n",
    "                    merge(i, j)\n",
    "        \n",
    "        return len(set(find(i) for i in range(m)))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
